package example.third_from_last;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 获取队列倒数第三个元素的值，要求：
 *      只能循环遍历一次，不能使用额外的数组等存储空间，且队列长度未知
 */
public class FindThirdToLast {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= 3; i++) {
            queue.add(i); // 添加元素 1 到 10
        }
        System.out.println(queue);
        System.out.println("==========");

        // 调用方法获取倒数第三个元素
        Integer result = findThirdToLast(queue.iterator());
        System.out.println("倒数第三个元素是: " + result);
    }

    public static <T> T findThirdToLast(Iterator<T> iterator) {
        // 初始化三个变量
        T first = null, second = null, third = null;

        // 遍历队列
        while (iterator.hasNext()) {
            // 滑动窗口更新
            first = second;
            second = third;
            third = iterator.next();
        }

        // 返回倒数第三个元素
        return first;
    }
}
